Masala #0969

Xotira 64 MB Vaqt 1250 ms Qiyinchiligi 59 %

3.2 (Baholar 5)

Sonlar o`qidagi girlyanda #1

Masalaning #1 va #2 versiyalari tubdan farq qiladi. Ularni alohida masalalar sifatida hisoblash to`g`riroqdir.

Yangi yilda arafasida, yangi yil ruhini bag`ishlovchi har xil bezak buyumlari mavjud. Asilbekka eng yoqgani - girlyandadir. Uni istalgan joyga ossa bo`ladi, devorga, mebelga, archaga... Asilbek esa girlyandani sonlar o`qiga osilganini ham ko`rgan!

Asilbek o`zining sevimli sonlar o`qining musbat tomoniga qarasa, u to`liq girlyanda bilan bezatilgan ekan. Bunda $a$ va $b(a \neq b)$ sonlar girlyanda bilan bog`langan, agarda $a|b$ yoki $b|a$ (bir sonni ikkinchisini qoldiqsiz bo`ladi) sharti qanoatlantirsa.

Payqash qiyin emaski, 1 sonidan girlyandalar orqali boshqa barcha sonlarga borish mumkin. Girlyanda orqali faqat katta songa o`tish mumkin bo`lsa, 1 sonidan $A$ sonigacha eng ko`pi bilan nechta o`tish yordamida yetib olsa bo`ladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - $T(1 \leq T \leq 2*10^5)$ testlar soni kiritiladi.

Keyingi $T$ ta qaorning har birida bittadan butun son - $A(2 \leq A \leq 10^7)$ soni kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda bitta butun son, masala javobini chop eting.

Misollar

#	input.txt	output.txt
1	3 12 4 7	3 2 1
2	2 100 8	4 3

Izoh:

1-test:

1 dan 12 ga yetish uchun eng uzun yo`l: 1 -> 2 -> 6 -> 12

2-test:

1 dan 100 ga yetish uchun eng uzun yo`l: 1 -> 5 -> 25 -> 50 -> 100

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin